#include "main/utils.h"
using namespace std;

bool isInterleave1(const string& s1,
                   const string& s2,
                   const string& s3) {
  int len1 = s1.size();
  int len2 = s2.size();
  int len3 = s3.size();
  if (len1 + len2 != len3)
    return false;

  vector<vector<bool>> dp;
  dp.resize(len1 + 1);
  for (int i = 0; i < len1 + 1; ++i) {
    dp[i].resize(len2 + 1, 0);
  }
  dp[0][0] = 1;
  for (int i = 0; i < len1; ++i) {
    dp[i + 1][0] = (s1[i] == s3[i] ? dp[i][0] : 0);
  }
  for (int j = 0; j < len2; ++j) {
    dp[0][j + 1] = (s2[j] == s3[j] ? dp[0][j] : 0);
  }
  for (int i = 0; i < len1; ++i) {
    for (int j = 0; j < len2; ++j) {
      int k = i + j + 1;
      dp[i + 1][j + 1] = (s1[i] == s3[k] && dp[i][j + 1]) || (s2[j] == s3[k] && dp[i + 1][j]);
      // if (s1[i] == s3[k] && s2[j] == s3[k]) {
      //   dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];
      // } else if (s1[i] == s3[k]) {
      //   dp[i + 1][j + 1] = dp[i][j + 1];
      // } else if (s2[j] == s3[k]) {
      //   dp[i + 1][j + 1] = dp[i + 1][j];
      // } else {
      //   dp[i + 1][j + 1] = 0;
      // }
    }
  }

  return dp[len1][len2];
}

bool isInterleave2(const string& s1,
                   const string& s2,
                   const string& s3) {
  int len1 = s1.size();
  int len2 = s2.size();
  int len3 = s3.size();
  if (len1 + len2 != len3)
    return false;

  vector<vector<bool>> dp;
  dp.resize(2);
  for (int i = 0; i < 2; ++i) {
    dp[i].resize(len2 + 1, 0);
  }
  dp[0][0] = 1;
  for (int j = 0; j < len2; ++j) {
    dp[0][j + 1] = (s2[j] == s3[j] ? dp[0][j] : 0);
  }
  for (int i = 0; i < len1; ++i) {
    dp[(i + 1) % 2][0] = (s1[i] == s3[i] ? dp[i % 2][0] : 0);
    for (int j = 0; j < len2; ++j) {
      int k = i + j + 1;
      dp[(i + 1) % 2][j + 1] = (s1[i] == s3[k] && dp[i % 2][j + 1]) ||
                               (s2[j] == s3[k] && dp[(i + 1) % 2][j]);
    }
  }

  return dp[len1 % 2][len2];
}

bool isInterleave3(const string& s1,
                   const string& s2,
                   const string& s3) {
  int len1 = s1.size();
  int len2 = s2.size();
  int len3 = s3.size();
  if (len1 + len2 != len3)
    return false;

  if (len1 < len2)
    return isInterleave3(s2, s1, s3);

  vector<bool> dp(len2 + 1, 0);
  dp[0] = 1;
  for (int j = 0; j < len2; ++j) {
    dp[j + 1] = (s2[j] == s3[j] ? dp[j] : 0);
  }
  for (int i = 0; i < len1; ++i) {
    dp[0] = (s1[i] == s3[i] ? dp[0] : 0);
    for (int j = 0; j < len2; ++j) {
      int k = i + j + 1;
      dp[j + 1] = (s1[i] == s3[k] && dp[j + 1]) ||
                  (s2[j] == s3[k] && dp[j]);
    }
  }

  return dp[len2];
}

int main() {
  string s1 = "aabcc";
  string s2 = "dbbca";
  string s3 = "aadbbcbcac";
  cout << isInterleave1(s1, s2, s3) << endl;
  cout << isInterleave2(s1, s2, s3) << endl;
  cout << isInterleave3(s1, s2, s3) << endl;

  return 0;
}
